#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void Print(int* array, int size)
{
  for(int i = 0; i < size;  i++){
    printf("%d ", array[i]);
  }
  printf("\n");
}

void Swap(int* pa1, int* pa2)
{
  int tmp = *pa1; 
  *pa1 = *pa2;
  *pa2 = tmp;
}

int GetMidIndex(int* array, int left, int right)
{
  int mid = (left + right) >> 1; 
  if(array[left] < array[mid]){
    if(array[left] > array[right]){
      return left;
    }
    else{
      if(array[mid] > array[right]){
        return right;
      }
      else return mid;
    }
  }
  else {
    //left > mid
    if(array[mid] > array[right]){
      return mid;
    }
    else{
      if(array[left] < array[right])
        return left;
      else return right;
    }
  }
}

//挖坑法
int Part1(int* array, int left, int right)
{
  Swap(&array[left], &array[GetMidIndex(array,left, right)]);
  int tmp = array[left];
  int begin = left;
  int end = right;
  while(begin <= end){
    while(begin < end && array[end] >= tmp) end--;
    array[begin] = array[end];
    while(begin < end && array[begin] <= tmp) begin++;
    array[end] = array[begin]; 
    if(begin == end) {
      array[begin] = tmp;
      break;
    }
  }

  return begin;
}

//前后指针法
int Part2(int* array, int left, int right)
{
  Swap(&array[left], &array[GetMidIndex(array, left, right)]);
  int keyi = left; 
  int fast = left + 1;
  int slow = left;
  while(fast <= right){
    if(array[fast] < array[keyi] && ++slow != fast){
      Swap(&array[fast], &array[slow]);
    }
    ++fast;
  }

  Swap(&array[slow], &array[keyi]);
  
  return slow;
}

//左右指针法
int Part3(int* array, int left, int right)
{
  Swap(&array[left], &array[GetMidIndex(array, left, right)]);
  int keyi = left;
  int begin = left;
  int end = right;
  while(begin <= end){
    while(begin < end && array[end] >= array[keyi]) end--;
    while(begin < end && array[begin] <= array[keyi]) begin++;
    if(begin != end) Swap(&array[begin], &array[end]);
    else {
      Swap(&array[begin], &array[keyi]);
      break;
    }
  }

  return begin;
}

void _RQuickSort(int* array, int left, int right)
{
  //需要>=防止段错误
  if(left >= right) return ;

  //int meeti = Part1(array, left, right);
  int meeti = Part2(array, left, right);
  //int meeti = Part3(array, left, right);

  _RQuickSort(array, left, meeti - 1);
  _RQuickSort(array, meeti + 1, right);
}

void RQuickSort(int* array, int size)
{
  int left = 0;
  int right = size - 1;
  _RQuickSort(array, left, right); 
}

void TestRQuickSort()
{
  int* array = (int*)malloc(sizeof(int) * 100);
  if(array == NULL){
    perror("malloc");
    return ;
  }

  for(int i = 0; i < 100; i++){
    array[i] = rand() % 100 + 1;
  }

  RQuickSort(array, 100);
  Print(array, 100);
  free(array);
}

int main()
{
  srand((unsigned long)time(NULL));
  TestRQuickSort();
  return 0;
}
